#include <unordered_map>
#include <vector>
using namespace std;

struct ListNode
{
    int val;
    ListNode*next ;
};

class Solution 
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if (lists.empty()) return nullptr;
        
        // 步骤1：合并所有链表
        ListNode* mergedHead = nullptr;
        ListNode* mergedTail = nullptr;
        
        // 这里没有问题

        for (auto list : lists) 
        {
            // 这里只是判空，不会终止循环，因为auto 会自己处理
            while (list != nullptr) 
            {
                // 为什么要手搭新的节点呢？？？
                ListNode* newNode = new ListNode(list->val);
                if (mergedHead == nullptr) 
                {
                    // 在平方时间内只发生了一次
                    mergedHead = newNode;
                    mergedTail = newNode;
                } 
                else 
                {
                    // 把新节点加入进来
                    mergedTail->next = newNode;
                    mergedTail = newNode;
                    // 先作为前一节点将新节点拼到这里，然后再把自己往前位移一步
                }
                // 继续 1:1 映射下一个节点

                list = list->next;
            }
        }
        
        // 步骤2：统计频率和确定范围
        unordered_map<int, int> freq;
        int minVal = INT_MAX, maxVal = INT_MIN;
        
        // 常规遍历操作
        ListNode* current = mergedHead;
        while (current != nullptr) 
        {
            // 获取最小值和最大值，复杂度真高
            freq[current->val]++;
            minVal = min(minVal, current->val);
            maxVal = max(maxVal, current->val);
            current = current->next;
        }
        
        // 步骤3：重新赋值
        // current节点回家重新遍历
        current = mergedHead;
        for (int val = minVal; val <= maxVal; val++) 
        {
            // .count是干什么的
            // 原来是检查键存在或不存在，那用find()行不行？？
            // 原来使用count更简洁！！！！
            if (freq.count(val)) 
            {
                // 循环n次，也就是添加给接下来n个节点赋值为当前值
                for (int i = 0; i < freq[val]; i++) 
                {
                    current->val = val;
                    current = current->next;
                }
            }
        }
        
        // 最后返回当前值
        return mergedHead;
    }
};